Unlike conventional wireless networks, such as cellular networks, ad-hoc networks do not have an infrastructure. Typically, ad-hoc networks use a large number of low complexity transceivers (nodes) to communicate information among each other. This approach not only decreases cost, but also decreases sensitivity to failure of a single link. This makes ad-hoc networks very promising for applications that require ultra-reliable communications links.
Highly reliable ad-hoc wireless networks have two contradictory constraints. The energy consumption has to be low, because the nodes are battery operated, and exhausting the battery can lead to failure. On the other hand, the probability for successful transmission of data should be very high. That is, a packet of data is to be transmitted from a source node to a destination node within a predetermined delay.
In ad-hoc networks, it is desired to select a route, i.e., a sequence of nodes, that passes the packet to the destination within a delay constraint, while minimizing energy. A simple solution uses a physical-layer transmission with a fixed packet size and coding rate, chosen so that that each link simply attempts to transmits a packet within a fixed span of time. Then, meeting the delay constraint is equivalent to limiting the number of hops.
However, this simple approach ignores the possibility of decreasing the overall delay by using more energy on certain links, and, possibly less on others. For a single link, the trade-off between transmission time and energy is straightforward. According to the Shannon's capacity equation, the possible data rate increases logarithmically with the transmit power. However, for networks with multiple hops, the trade-off becomes much more complicated. It involves selecting a route and then an energy level for each hop along the route.
In a unicast network of N nodes, each nodes can trade-off transmission power and transmission time using adaptive modulation and coding (AMC). A transmission is only considered successful if the packet arrives at the destination within the delay constraint. It is desired select a route and a per-hop energy assignment that minimizes the overall energy expenditure while at the same time enabling a probability of successful transmission of q, where q is in the range of 90, 99.999%.
Typically, only statistics of the channel state information (CSI) are available for the routing because the CSI is dynamic in ad-hoc networks. The coherence times of wireless propagation channels, i.e., the required update interval, is on the order of a few milliseconds. Frequently updating the CSI throughout the network would lead to unacceptable overhead. In large networks, the overhead traffic communicating the routing information for all possible links would decrease spectral efficiency and battery lifetime. On the other hand, on-demand route discovery is not feasible because the route discovery process often takes longer than the delay constraint.
Thus, the problem is well defined and practically relevant, but extremely hard to solve. There are on the order of N! possible routes in a network of N nodes, and for each route, the transmit energies of the nodes has to be optimized under probabilistic constraints.
One method considers delay constraints, but only with respect to scheduling on a single link, Berry et al., “Communication over fading channels with delay constraints,” IEEE Transactions on Information Theory, vol. 48, pp. 1135-1149, 2002. Other methods consider energy/delay trade-off, but again only on a single link, Zhong et al., “Delay-constrained energy-efficient wireless packet scheduling with QoS guarantees,” and Yang et al., “Energy minimization for real-time data gathering in wireless sensor networks,” in IEEE Trans. Wireless Communications, vol. 5, 2006.
A number of methods consider joint routing and power control, but under the assumption of instantaneous CSI, and without delay constraints, Cruz et al. “Optimal link scheduling and power control in CDMA multihop wireless networks,” IEEE Globecom, 2002. Another method considers routing with probabilistic delay constraints, but assumes fixed transmit power for each node, and convex bounds, U.S. patent application, Ser. No. filed by Brand, et al., on